from collections import defaultdict, deque
from typing import List


class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        # 预处理可达
        edges = defaultdict(list)
        wordList = wordList + [beginWord]
        if endWord not in wordList: return []
        def diff(w1, w2):
            n = len(w1)
            cnt = 0
            for i in range(n):
                if w1[i] != w2[i]: cnt += 1
                if cnt > 1: return False
            return cnt == 1

        for i in range(len(wordList)):
            for j in range(i):
                if diff(wordList[i], wordList[j]):
                    edges[wordList[i]].append(wordList[j])
                    edges[wordList[j]].append(wordList[i])
        # bfs
        q = deque([(beginWord, 0, [])])
        ans = []
        visited = set()
        while q:
            word, cost, road = q.popleft()
            if ans and cost > len(ans[0]):
                continue
            road.append(word)
            if word == endWord:
                ans.append(road[:])
            if word in visited: continue
            visited.add(word)

            for nword in edges[word]:
                q.append([nword, cost+1, road[:]])
        return ans

if __name__ == '__main__':
    s = Solution()
    r = s.findLadders(beginWord = "red", endWord = "tax", wordList = ["ted","tex","red","tax","tad","den","rex","pee"] )
    print(r)